Field of the Invention
The various embodiments of the invention described herein relate generally to microprocessor cache subsystems in computer systems. and more specifically to cache replacement policies.
Description of the Related Art
High performance caching is critical to system performance as it helps keeping relevant data close to the computing or processing units that need it, which in turn reduces the number for costly (e.g., long-latency) accesses to main memory or lower level caches for fetching missing data. One key aspect in designing a high-performing cache is the choice of a replacement policy. Ideally, a cache line replacement policy should remove and/or replace any cache lines that will not be referenced again in the near future. The Least Recently Used (LRU) cache line replacement policy aims to approximate this by assuming that if a cache line has not been used for a while, it is unlikely to be used again.
The implementation of a perfect LRU policy in hardware, however, is a costly proposition in terms of time and space requirements. For example, a full LRU implementation capable of tracking exactly the age each cache line in the cache requires at least N number of bits, where N=log(cache_associativity). Moreover, these N bits need to be updated each time data in the cache is accessed, which also incurs significant maintenance overhead. Thus, to reduce the number of resources required, some form of a pseudo LRU implementation is often used instead. For instance, some pseudo LRU implementations utilize a fixed-number of bits (e.g., 2-bits) for tracking the cache line age regardless of cache associativity. This not only simplifies the implementation but also reduces the time and space requirements, in exchange for not being able to precisely track each cache line's age. One of the tradeoffs of this simplified approach is that it often resulted in multiple eviction candidates and whichever candidate that happens to be found or scanned first will be evicted. This represents a potential drawback because the selected eviction choice may not always be ideal as 1) the chosen cache line may have better locality than the other candidates, and 2) the chosen cache line may reside in a remote cache slice or distant memory that is more costly to fetch from when it is referenced again.